Efficient lookup is an important task in many computer information systems. Routing a message to a correct recipient may require efficient lookup in a routing data structure. Additionally or alternatively, retrieving stored information may also require lookup in a relevant data structure.
A Bloom filter is a probabilistic data structure that can represent set membership in an approximate manner. A Bloom filter responds to membership queries without false negatives, but may provide a false positive at a bounded rate. That is, a query to the filter on whether x is in the set is always correct if item x was inserted into the set S, but may err when the item x in not in S (false positive). Using Bloom filters to represent list of items that are being looked-up may provide significant space saving.
In some cases, multiple Bloom filters are used to represent a set of different lists. For example, each filter representing a different potential destination and a list of cases in which the message will be routed to that destination. As an example, in a cluster of servers, a Bloom filter may be used to determine whether to distribute a message to a certain server.
One major drawback of using multiple Bloom filters is that one needs to do multiple Bloom filter lookups to determine the correct routing. Performing a lookup into a Bloom filter incurs two main costs: first is the computation of up to k hash function values on the key string, and then the retrieval of up to k bits from memory, where each bit resides in address(k)=base+offset(k), where offset(k) is the index calculated by the k-th hash function.